A warm climate on early Mars would provide a natural, although not unique, explanation for the presence of fluvial networks on the ancient, heavily cratered terrains. Explaining how the climate could have been kept warm, however, is not easy. The idea that the global average surface temperature, T(sub s), could have been kept warm by a dense, CO2 atmosphere supplied by volcanism or impacts is no longer viable. It was shown that CO2 cloud formation should have kept T(sub s) well below freezing until approximately 2 b.y. ago, when the Sun had brightened to at least 86 percent of its present value. Warm equatorial regions on an otherwise cold planet seem unlikely because atmospheric CO2 would probably condense out at the poles. Warming by impact-produced dust in the atmosphere seems unlikely because the amount of warming expected for silicate dust particles is relatively small. Greenhouse warming by high altitude CO2 ice clouds seems unlikely because such are poor absorbers of infrared radiation at most wavelengths. Warming by atmospheric NH3 seems unlikely because NH3 is readily photodissociated and because N may have been in short supply as consequence of impact erosion and the high solubility of NH3. A brighter, mass-losing young Sun seems unlikely because stellar winds of the required strength were not observed on other solar-type stars. In short, most of the explanations for a warm Martian paleoclimate that were proposed in the past seem unlikely. One possibility that seems feasible from radiative/photochemical standpoint is that CH4 and associated hydrocarbon gases and particles contributed substantially to the greenhouse effect on early Mars. Methane is photochemically more stable than NH3 and the gases and particles that can be formed from it are all good absorbers of infrared radiation. The idea of a CH4-rich Martian paleoatmosphere was suggested a long time ago but has fallen out of favor because of perceived difficulties in maintaining a CH4-rich atmosphere. In particular, it is not obvious where the CH4 might come from, since volcanic gases (on Earth, at least) contain very little CH4. This difficulty could be largely overcome if early Mars was inhabited by microorganisms. Then, methanogenic bacteria living in sediments could presumably have supplied CH4 to the atmosphere in copious quantities.